package com.lwl.shua.class03;

import java.util.Arrays;

/**
 * @author lwl
 * @Description TODO
 * @date 2025/9/10 14:48
 */
public class Code06Lc1755MinAbsDifference {
    public static void main(String[] args) {
        System.out.println(minAbsDifference(new int[]{7, -9, 15, -2}, -5));
    }

    // 为什么是20次方呢？因为nums的长度最大为40，采用分治后，左右数组每个位置取或不取，结果就有2的20次方次
    public static int[] lArray = new int[1 << 20];
    public static int[] rArray = new int[1 << 20];

    public static int minAbsDifference(int[] nums, int goal) {
        if (nums == null || nums.length == 0) {
            return goal;
        }
        int lCount = process(nums, 0, nums.length / 2, 0, 0, lArray);
        int rCount = process(nums, nums.length / 2, nums.length, 0, 0, rArray);
        Arrays.sort(lArray, 0, lCount);
        Arrays.sort(rArray, 0, rCount);
        int rIndex = rCount - 1;
        int res = Math.abs(goal);
        for (int i = 0; i < lCount; i++) {
            int rest = goal - lArray[i];
            // 如果下一个rIndex比当前小，就取下一个
            while (rIndex > 0 && Math.abs(rest - rArray[rIndex]) >= Math.abs(rest - rArray[rIndex - 1])) {
                rIndex--;
            }
            res = Math.min(res, Math.abs(rest - rArray[rIndex]));
        }
        return res;
    }

    private static int process(int[] nums, int index, int end, int sum, int fillIndex, int[] array) {
        if (index == end) {
            // 这里++是为了下一次递归填入下一个位置，因为fill是会返回的，用于下次递归的入参
            array[fillIndex++] = sum;
        } else {
            fillIndex = process(nums, index + 1, end, sum + nums[index], fillIndex, array);
            fillIndex = process(nums, index + 1, end, sum, fillIndex, array);
        }
        return fillIndex;
    }
}
